1. Technical Field
The present disclosure relates to a binary magnitude comparator and a binary magnitude comparator based content addressable memory cell.
2. Description of Related Art
A binary number comparator is applied to receive two n-bit binary number, i.e. the compariers A=(An-1An-2 . . . A1A0)2 and B=(Bn-1Bn-2 . . . B1B0)2, and to output at least one Boolean value to represent at least one of the following magnitude relations: G means A is greater than B, E means A is equal to B, L means A is less than B, LE or G means A is not greater than B, GE or L means A is not less than B, and GL or Ē means A is not equal to B.
The one bit comparator can be modified by the Karnaugh map or the Mac Klusky algorithm, and usually requires 20 transistors to achieve the logical circuit. As described in T. V. Le. “High-speed magnitude comparator circuit,” U.S. Pat. No. 5,281,946, Jan. 25, 1994, the n-bit binary number comparator that can deal more than one bit has to propagate the equality from the most significant bit to the least significant bit, and thus the computation time is increased.
Taiwan patent number 528982 provides a carry look-ahead adder to accelerate the n-bit binary number comparator. However, it requires large circuit area and rises bit carry issue and bit borrow issue.
Except by using the adders to achieve the n-bit binary number comparator, a serial type n-bit binary number comparator and a parallel type n-bit binary number comparator are disclosed. The serial type n-bit binary number comparator requires many pulse cycles to complete the comparison and thus the computation time is increased. The parallel type n-bit binary number comparators, such as the four strings parallels comparator described in U.S. Pat. No. 3,519,347 and the tree structure comparator described in U.S. Pat. No. 7,403,407, suffer the drawback of requiring large circuit area.
FIG. 1 is a circuit of a comparator in U.S. Pat. No. 7,016,931 of the prior. The comparator 100 uses the logic structures 110, 120, 130 to propagate the equality from the source and the ground terminal to the output terminal. Once the bits in higher place are equal to each other and the stack transistors are interrupted, such as the logic structure 120 is interrupted, the relation result decided by the bits in lower place is applied to decide whether the output is pulled down or not. Therefore, each logic structure 120 of the comparator 100 requires merely 15 transistors included to achieve the XOR gate and the NOT gate.
The content addressable memory (CAM) is broadly applied in the quick searching and matching systems such as the computer cache system and the net address look aside interface. The CAM is separated into two categories by the logic function, i.e. the binary CAM (SCAM) and the ternary CAM (TCAM). The CAM is separated into two categories by the structure of the memory cell, i.e. the static random access memory (SRAM) and the dynamic random access memory (DRAM). The SRAM is faster and stable but requires more transistors than the DRAM. No matter which kind of memory cell is selected to collocate the BCAM or the TCAM, the matching mechanism is limited by figuring out the equal or don't care relations of the bits one by one.
As described in U.S. Pat. No. 6,987,683, the stored values are sorted to improve the efficiency when searching an address. However, the circuit requires many transistors since the thresholds, the priorities or the weights have to be determined before searching.
As described in U.S. Pat. No. 7,403,407, the circuit is simplified but still requires 12 transistors to achieve the basic functions, let alone the extra circuit to propagate the equality. As described above, the comparators in prior system suffer many drawbacks such as large circuit area, many required transistors and cannot be embedded into the comparable content addressable memory (CCAM).